In a wireless communication system such as cellular or Personal Communications Services, base stations are located such that radio signals are available through out the service area. To obtain near seamless coverage, many cells are required. Predicting the coverage of such cells is a difficult job, and a number of tools have been developed which make some use of terrain data, with building clutter information, such as that available by the US Geological Survey within the United States. This data is used in conjunction with models that are well known in the art, such as the Longley-Rice model which uses base and subscriber heights, along with a description of the terrain to calculate a prediction of the expected propagation loss for the locations under consideration.
This method works sufficiently well for large cells whose base antenna is well above the building clutter, so the influence of particular buildings/structures or groups of buildings is minimal. When the base station antennas are near rooftop level or below building rooftops, then the actual size and shape of the buildings influences the signals as they propagate down the streets and diffract around corners. These cells, generally called microcells, typically cover a much smaller area, especially in dense urban areas. Tools to predict micro-cell coverage typically use information about the building sizes, shapes, and sometimes material types to aid in modeling the propagation paths in and around the buildings in the coverage area.
A deterministic process, as opposed to the above statistical process, basically attempts to model the radiowave propagation as rays radiating from the transmitter to the receiver. This approach can be effective and accurate when the objects in the modeled environment are much larger in dimension than the wave length of the transmitted signal. The propagation phenomena that can be modeled in a ray-tracing process include reflection, diffraction, transmission and the combinations of the above. Within ray tracing there are two generally known approaches. The first is called the "shooting-and-bouncing" method, in which a fixed number of rays are launched from the source (transmitter), then forward-traced to follow the different propagation paths, with a ray being terminated when it hits a detection sphere at the receiver. A major advantage of this approach is that it can be applied to most any type of surface. A key disadvantage is that for every receiver location, the rays have to be launched and traced again in all directions. This could mean hours or even days of computation time for a practical environment.
The second method is based on image theory, which is traditionally limited to more or less planar surfaces in the environment. The basic notion here is that the images of a source at a fixed location in a given environment are independent of the location of the point of observation (receiver) as long as there are basically planar surfaces in the environment. Therefore one can build all the images for a given location of the source and environment and reuse it for as many receiver locations as one needs. This represents an improvement in terms of computational efficiency, but of course, one is limited by the planar surfaces in the environment. This is, however, typical of an urban microcellular environment. Thus, a conventional image theory approach may be advantageously used for microcells, with one first determining an image tree (hierarchically organized for ease of use) based on the location of the source in the environment and the environment itself. The environment consists of mirrors (or reflective surfaces) and corners. Starting from the source image, each mirror or corner has the potential of generating a "child" image from the source image. Each child image can further generate child images for every mirror and every corner. Once the image tree is built, for a given receiver location every image on the tree needs to be examined to see whether it contributes to the total received power through a back-tracing process from the receiver to the transmitter.
However, a key problem with image tracing is the size of the image tree for a realistic environment, leading to very large computational and memory requirements. The following example illustrates the problem. In an environment defined by N mirrors, there are also (typically) approximately N corners. Each of the N mirrors can potentially generate a reflective image, and each of the N corners can potentially generate a diffractive image. Without some limitation on the growth of the image tree, a source with m levels of reflection and n levels of diffraction will generate on the order of (2N).sup.n N.sup.(m-n) images, assuming m&gt;n. For example, if N=100, m=3, n=1, then a conventional image tree will include about 2,000,000 images. If each image object takes 100 bytes of memory (i.e., in order to hold its own attributes and pointers to its ancestor image and descendant images), the total memory needed to hold the above image tree with fairly modest assumptions is 200 megabytes! Given the number of images involved, it is typical for the process of determining transmitter/receiver placements to take days or even weeks, depending on the number of buildings or other structures, the size of the coverage area, and the resolution of the calculated grid of predicted points.
Because of the large computational requirements in prior ray tracing approaches, no attempt has been made to use calculated results in determining optimal placement of anything more than single antenna sites. However, most base stations employ more than one antenna, typically to compensate for short or Rayleigh fading over the communication channel via diversity. By only determining placement based on uniform propagation from a single antenna, without consideration of possible improvements of micro-diversity (e.g., placement to compensate for Rayleigh fading) or macro-diversity (e.g., placement to compensate for log normal fading), possible adjustments in the variations in the placement of diversity antennas is foregone.
There remains therefore a need for an improved method of ray tracing which compensates for these and other problems, including providing a computationally efficient method for ray tracing, and using propagation estimates from ray tracing to optimize antenna placement.